class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n=prices.length;
        int dp1=-prices[0];
        int dp2=0;

        for(int i=1;i<n;i++){
            int newDp1=Math.max(dp1,dp2-prices[i]);
            int newDp2=Math.max(dp2,(dp1+prices[i]-fee));

            dp1=newDp1;
            dp2=newDp2;

        }

        return dp2;

    }
}


class Solution1{
    public int maxProfit(int[] prices) {
        int n=prices.length;
        int[][] dp1=new int[n][3];
        int[][] dp2=new int[n][3];

        dp1[0][0]=-prices[0];
        dp1[0][1]=-prices[0];
        dp1[0][2]=-prices[0];

        dp2[0][0]=0;





        for(int i=1;i<n;i++){

            for(int j=0;j<3;j++){
                dp1[i][j]=Math.max(dp1[i-1][j],dp2[i-1][j]-prices[i]);
                if(j>0) dp2[i][j]=Math.max(dp1[i-1][j-1]+prices[i],dp2[i-1][j]);

            }
        }
        return Math.max(dp2[n-1][0],Math.max(dp2[n-1][2],dp2[n-1][1]));
    }
}


class Solution2 {
    public int maxProfit(int k, int[] prices) {
        int n=prices.length;
        int[][] dp1=new int[n][k+1];
        int[][] dp2=new int[n][k+1];
        k++;

        for(int i=0;i<k;i++){
            dp1[0][i]=-prices[0];

        }


        for(int i=1;i<n;i++){

            for(int j=0;j<k;j++){
                dp1[i][j]=Math.max(dp1[i-1][j],dp2[i-1][j]-prices[i]);
                if(j>0) dp2[i][j]=Math.max(dp1[i-1][j-1]+prices[i],dp2[i-1][j]);

            }
        }

        int maxVal=0;

        for(int i=0;i<k;i++){
            maxVal=Math.max(maxVal,dp2[n-1][i]);
        }
        return maxVal;
    }
}